home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / irit / bool2low.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  37.6 KB  |  1,009 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)!    *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersecting polyline between the oprnds.  *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. *****************************************************************************/
  18.  
  19. /* #define DEBUG        If defined, return intersection POLYLINE object. */
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #include <stdio.h>
  24. #include <ctype.h>
  25. #include <math.h>
  26. #include <string.h>
  27. #include "program.h"
  28. #include "allocate.h"
  29. #include "booleang.h"
  30. #include "booleanl.h"
  31. #include "convex.h"
  32. #include "geomat3d.h"
  33. #include "intrnrml.h"
  34. #include "objects.h"
  35.  
  36. static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB);
  37. static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
  38.                     InterSegListStruct *OLoop, int AinB);
  39. static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
  40.                             IPPolygonStruct *Pl);
  41. static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn);
  42. static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt);
  43. static CombineClosedLoops(IPPolygonStruct *Pl, InterSegListStruct *PClosed,
  44.                                 int AinB);
  45. static void PushAdjOnStack(IPPolygonStruct *Pl, IPPolygonStruct *AdjStack[],
  46.                              int *StackPointer);
  47. static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
  48.                        IPPolygonStruct *Pl2);
  49.  
  50. #ifdef DEBUG2
  51. static void PrintVrtxList(IPVertexStruct *V);
  52. static void PrintInterList(InterSegmentStruct *PInt);
  53. #endif /* DEBUG2 */
  54.  
  55. /*****************************************************************************
  56. *   Test on which side of polygon Pl, given Point V is, and according to     *
  57. * the requirement (AinB) returns TRUE/FALSE.                     *
  58. *   If test on V fails, we tries the next one V -> Pnext until success...    *
  59. *****************************************************************************/
  60. static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB)
  61. {
  62.     int In;
  63.     RealType Distance;
  64.     IPVertexStruct
  65.     *VHead = V;
  66.  
  67.     do {
  68.     Distance = Pl -> Plane[0] * V -> Coord[0] +
  69.            Pl -> Plane[1] * V -> Coord[1] +
  70.            Pl -> Plane[2] * V -> Coord[2] + Pl -> Plane[3];
  71.     In = Distance > 0.0;
  72.     V = V -> Pnext;
  73.     }
  74.     while (ABS(Distance) < EPSILON && V != NULL && V != VHead);
  75.  
  76.     if (ABS(Distance) < EPSILON)
  77.     IritFatalError("TestAInB: Failed to find non coplanar point.");
  78.  
  79.     return (In && AinB) || (!In && !AinB);   /* I wish I had logical XOR ... */
  80. }
  81.  
  82. /*****************************************************************************
  83. *   Convert an inter loop into an open vertex list.                 *
  84. *****************************************************************************/
  85. IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
  86. {
  87.     IPVertexStruct *VHead, *V;
  88.  
  89.     VHead = V = IPAllocVertex(0, 0, NULL, NULL);
  90.  
  91.     PT_COPY(VHead -> Coord, PIHead -> PtSeg[0]);
  92.  
  93.     while (PIHead != NULL) {
  94.     V -> Pnext = IPAllocVertex(0, 0, NULL, NULL);
  95.     V = V -> Pnext;
  96.     PT_COPY(V -> Coord, PIHead -> PtSeg[1]);
  97.  
  98.     PIHead = PIHead -> Pnext;
  99.     }
  100.  
  101.     V -> Pnext = NULL;
  102.  
  103.     return VHead;
  104. }
  105.  
  106. /*****************************************************************************
  107. *   Clip an open loop from a polygon:                         *
  108. * 1. Clip the section (S) of the polygon between the two loop end points and *
  109. *    replace it by the loop itself.                         *
  110. * 2. If the polygon formed from S and the loop should be in the output       *
  111. *    (as tested by AinB) return that polygon. Otherwise return NULL.         *
  112. *   The open loop itself (excluding the header OLoop) is freed.             *
  113. * Note it is assumed (ordered by the sorting routines above) that the open   *
  114. * loop starts from the second end back to first:                 *
  115. *                                         *
  116. *                   L1-----------------------L2             *
  117. *                |            |             *
  118. *                |L0            |L3             *
  119. *    *---------------*-------+----*-------------*----+-----------*         *
  120. *    P0        P1         P2           P3            P0         *
  121. *****************************************************************************/
  122. static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
  123.                     InterSegListStruct *OLoop, int AinB)
  124. {
  125.     int GenClipPoly;        /* TRUE if needs to form polygon from S & OLoop. */
  126.     IPVertexStruct *VStart, *VEnd, *VEnd1,    /* Corresponds to L0 and L3... */
  127.     *ClipPoly,            /* The clipped element from polygon. */
  128.     *PLoop,                  /* The loop itself as vertex list. */
  129.     *PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2,
  130.     *PRevLoop = NULL;
  131.     InterSegmentStruct *PISeg, *PItemp;
  132.     IPPolygonStruct *ClipPl;
  133.  
  134. #ifdef DEBUG3
  135.     printf("Enter ClipOpenLoopFromPoly\n");
  136. #endif /* DEBUG3 */
  137.  
  138.     PISeg = OLoop -> PISeg;
  139.     VStart = PISeg -> V[0];
  140.     while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
  141.     VEnd = PISeg -> V[1];
  142.     if (VStart == NULL || VEnd == NULL)
  143.     IritFatalError("ClipOpenLoopFromPoly: None open loop");
  144.     VEnd1 = VEnd;           /* Find the pointer thats points on VEnd. */
  145.     while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;
  146.  
  147.     PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
  148.     PLoopEnd = PLoop;              /* Prepare pointer on last vertex. */
  149.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  150.     PLoopEnd1 = PLoop;
  151.     while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;
  152.  
  153.     if (VStart != VEnd) {
  154.     /* Now we test if we need to create a polygon formed from S & open   */
  155.     /* loop by testing on which side of the polygon that caused         */
  156.     /* intersection L0L1, point P2 is, and compare with requirement AinB.*/
  157.     GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);
  158.  
  159.     /* Keep the clipped VertexList P2, P3 & substitute with open loop:   */
  160.     /* Note we must keep vertex VEnd in the polygon as another InterSeg. */
  161.     /* may point on it, so we replace InterSeg point (L3) by (P3) and    */
  162.     /* leave VEnd intact.                             */
  163.     Ptemp1 = VEnd -> Pnext;             /* Save that pointer temporary. */
  164.     VEnd -> Pnext = NULL;           /* Close the clipped vertex list. */
  165.  
  166.     PT_SWAP(VEnd -> Coord, PLoopEnd -> Coord);
  167.     PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal);
  168.     VEnd1 -> Pnext = PLoopEnd;
  169.     PLoopEnd1 -> Pnext = VEnd;
  170.     PLoopEnd -> Count = VEnd -> Count;
  171.     PLoopEnd -> Tags = VEnd -> Tags;
  172.  
  173.     Ptemp2 = VEnd;
  174.     VEnd = PLoopEnd;
  175.     PLoopEnd = Ptemp2;
  176.  
  177.     ClipPoly = VStart -> Pnext;
  178.  
  179.     /* New ClipPoly is isolated (Open loop of P2, P3 only). Save         */
  180.     /* reversed list of open loop if we need to form an S/OLoop polygon, */
  181.     /* otherwise free ClipPoly. Chain the OLoop instead of S.         */
  182.     if (GenClipPoly)
  183.         PRevLoop = GenReverseVrtxList(PLoop);
  184.     else
  185.         IPFreeVertexList(ClipPoly);
  186.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  187.     PLoopEnd -> Pnext = Ptemp1;
  188.     }
  189.     else { /* VStart == VEnd */
  190.     /* Now we test if we need to create a polygon formed from S & open   */
  191.     /* loop by testing on which side of the polygon that caused         */
  192.     /* intersection L0L1, point L3 is, and compare with requirement AinB.*/
  193.     GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);
  194.  
  195.     /* In this case the clipped part is empty, so its simpler: */
  196.     ClipPoly = NULL;
  197.  
  198.     /* Save reversed list of open loop if we need to form an S/OLoop     */
  199.     /* polygon. Chain the OLoop instead of S.                 */
  200.     if (GenClipPoly)
  201.         PRevLoop = GenReverseVrtxList(PLoop);
  202.  
  203.     PLoopEnd -> Pnext = VEnd -> Pnext;
  204.     PLoopEnd -> Tags = VEnd -> Tags;
  205.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  206.     }
  207.  
  208.     /* Time to free the InterSegment list pointed by OLoop: */
  209.     PISeg = OLoop -> PISeg;
  210.     while (PISeg != NULL) {
  211.     PItemp = PISeg;
  212.     PISeg = PISeg -> Pnext;
  213.     IritFree((VoidPtr) PItemp);
  214.     }
  215.     OLoop -> PISeg = NULL;            /* To be on the safe side... */
  216.  
  217.     /* There is a chance that Pl -> PVertex will point on vertex in clipped  */
  218.     /* part so we update it to point on VStart, which for sure is in polygon.*/
  219.     Pl -> PVertex = VStart;
  220.     if (GenClipPoly) {       /* Generate the polygon from ClipPoly & PRevLoop: */
  221.     PLoopEnd = PRevLoop;
  222.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  223.  
  224.     if (ClipPoly == NULL) {
  225.         PLoopEnd -> Pnext = PRevLoop;  /* Close that loop and return it. */
  226.         ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  227.                     PRevLoop, NULL);
  228.         PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  229.         IP_RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  230.         return ClipPl;
  231.     }
  232.  
  233.     PLoopEnd -> Pnext = ClipPoly;
  234.     PLoopEnd -> Tags = VStart -> Tags;
  235.     PLoopEnd -> Count = VStart -> Count;
  236.     Ptemp1 = ClipPoly;
  237.     while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
  238.     Ptemp1 -> Pnext = PRevLoop;
  239.  
  240.     ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  241.                 ClipPoly, NULL);
  242.     PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  243.     IP_RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  244.     return ClipPl;
  245.     }
  246.     else
  247.     return NULL;
  248. }
  249.  
  250. /*****************************************************************************
  251. *   Create a new vertex list, in reverse order. The original is not modified.*
  252. *****************************************************************************/
  253. static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn)
  254. {
  255.     IPVertexStruct *VOutHead, *VOut;
  256.  
  257.     VOutHead = IPAllocVertex(0, 0, NULL, NULL);
  258.  
  259.     PT_COPY(VOutHead -> Coord, VIn -> Coord);
  260.     VIn = VIn -> Pnext;
  261.  
  262.     while (VIn != NULL) {
  263.     VOut = IPAllocVertex(0, 0, NULL, NULL);
  264.     PT_COPY(VOut -> Coord, VIn -> Coord);
  265.     PT_COPY(VOut -> Normal, VIn -> Normal);
  266.  
  267.     VOut -> Pnext = VOutHead;         /* Chain them in reverse order. */
  268.     VOutHead = VOut;
  269.  
  270.     VIn = VIn -> Pnext;
  271.     }
  272.  
  273.     return VOutHead;
  274. }
  275.  
  276. /*****************************************************************************
  277. * Find the intersection of the ray fired from Pt to +X direction with the    *
  278. * given polygon. Note Pt MUST be in the polygon. Two vertices equal to         *
  279. * ray/polygon intersection point are added to polygon vertex list, and a     *
  280. * pointer to the first one is also returned. This routine is exclusively     *
  281. * used by the CombineClosedLoops below.                         *
  282. * The polygon is NOT assumed to be convex and we look for the minimum X      *
  283. * intersection. The polygon might not be convex as a result of combinning    *
  284. * some other closed loop before the current one...                 *
  285. *****************************************************************************/
  286. static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt)
  287. {
  288.     int OnVertex = FALSE;
  289.     RealType X,
  290.     MinX = INFINITY;
  291.     IPVertexStruct *V, *Vnext,
  292.     *VMinX = NULL;
  293.  
  294.     V = Pl -> PVertex;
  295.     do {
  296.     Vnext = V -> Pnext;
  297.  
  298.     /* A polygon edge might intersect the ray iff one of the following:  */
  299.     /* 1. The first vertex is exactly on the ray Y level. (if this is    */
  300.     /*    true for the second edge, it will be detected next iteration). */
  301.     /* 2. The first vertex is below ray Y level, and second is above.    */
  302.     /* 3. The first vertex is above ray Y level, and second is below.    */
  303.     if (APX_EQ(V -> Coord[1], Pt[1])) {            /* Case 1 above. */
  304.         if (MinX > V -> Coord[0] && Pt[0] < V -> Coord[0]) {
  305.         OnVertex = TRUE;
  306.         MinX = V -> Coord[0];
  307.         VMinX = V;
  308.         }
  309.     }
  310.     else if ((V -> Coord[1] < Pt[1] &&
  311.           Vnext -> Coord[1] > Pt[1]) || /* Case 2. */
  312.          (V -> Coord[1] > Pt[1] &&
  313.           Vnext -> Coord[1] < Pt[1])) { /* Case 3. */
  314.         X = ((Vnext -> Coord[1] - Pt[1]) * V -> Coord[0] +
  315.          (Pt[1] - V -> Coord[1]) * Vnext -> Coord[0]) /
  316.         (Vnext -> Coord[1] - V -> Coord[1]);
  317.         if (MinX > X && Pt[0] < X) {
  318.         OnVertex = FALSE;
  319.         MinX = X;
  320.         VMinX = V;
  321.         }
  322.  
  323.     }
  324.  
  325.     V = Vnext;
  326.     }
  327.     while (V != NULL && V != Pl -> PVertex);
  328.  
  329.     if ((V = VMinX) == NULL)
  330.     IritFatalError("CutPolygonAtRay: fail to find intersection");
  331.  
  332.     /* Now that we have the intersection point - create two new vertices     */
  333.     /* (one if OnVertex), insert them (it) after V and return the first.     */
  334.     if (OnVertex) {
  335.     V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  336.     PT_COPY(V -> Pnext -> Coord, V -> Coord);
  337.     PT_CLEAR(V -> Pnext -> Normal);
  338.     V -> Tags = V -> Count = 0;
  339.     }
  340.     else {
  341.     V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  342.     Vnext = V -> Pnext;
  343.     Vnext -> Coord[0] = MinX;     /* X - as intersection point found. */
  344.     Vnext -> Coord[1] = Pt[1];          /* Y - must be as ray Y level. */
  345.     Vnext -> Coord[2] = V -> Coord[2];/* Z - all polys has same Z value. */
  346.  
  347.     V -> Pnext = IPAllocVertex(0, 0, NULL, V -> Pnext);
  348.     V = V -> Pnext;
  349.     PT_COPY(V -> Coord, Vnext -> Coord);
  350.     PT_CLEAR(V -> Normal);
  351.     }
  352.  
  353.     return V;
  354. }
  355.  
  356. /*****************************************************************************
  357. *   Convert the given closed loop list to polygons, and return them. the     *
  358. * original given polygon vertex list is freed, and the first loop is subst.  *
  359. * instead.                                     *
  360. *****************************************************************************/
  361. static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
  362.                             IPPolygonStruct *Pl)
  363. {
  364.     int LoopNum = 0;
  365.     IPVertexStruct *V, *VHead;
  366.     InterSegmentStruct *PISeg, *PItemp;
  367.     InterSegListStruct *PClosedTemp;
  368.  
  369.     IPFreeVertexList(Pl -> PVertex);
  370.     Pl -> Pnext = NULL;
  371.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  372.  
  373.     while (PClosed != NULL) {
  374.     /* Convert the InterList to vertex list and free the first: */
  375.     V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
  376.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  377.         IritFatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");
  378.  
  379.     PISeg = PClosed -> PISeg;      /* Time to free the InterSegmentList: */
  380.     while (PISeg != NULL) {
  381.         PItemp = PISeg;
  382.         PISeg = PISeg -> Pnext;
  383.         IritFree((VoidPtr) PItemp);
  384.     }
  385.  
  386.     while (V -> Pnext -> Pnext != NULL)
  387.         V = V -> Pnext;                   /* Go to last pt. */
  388.     IPFreeVertex(V -> Pnext);        /* and free - same as first. */
  389.     V -> Pnext = VHead;               /* Make vertex list circular. */
  390.  
  391.     if (LoopNum++) {
  392.         Pl -> Pnext = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  393.                      VHead, Pl -> Pnext);
  394.         PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
  395.     }
  396.     else {
  397.         Pl -> PVertex = VHead;
  398.     }
  399.  
  400.     PClosedTemp = PClosed;
  401.     PClosed = PClosed -> Pnext;
  402.     IritFree((VoidPtr) PClosedTemp);
  403.     }
  404. }
  405.  
  406. /*****************************************************************************
  407. *   This routines cuts the given polygon into its interior closed loops by   *
  408. * adding an edge from the polygon boundary to each of its closed loops.      *
  409. *   For example:                                 *
  410. *                                         *
  411. * +-----------------------+      +-----------------------+             *
  412. * |                       |     |                       |             *
  413. * |  / \         / \      |     |  / \________ / \      |             *
  414. * |  \ /        |   |     |     |  \ /        |   |_____|             *
  415. * |      _       \ /      | -->  |      _       \ /      |             *
  416. * |     / \_              | -->  |     / \_              |             *
  417. * |    |    |             |     |    |    |_____________|             *
  418. * |     \__/              |     |     \__/              |             *
  419. * |                       |      |                       |             *
  420. * +-----------------------+      +-----------------------+             *
  421. *                                         *
  422. *   Algorithm:                                     *
  423. * 1. Transform the polygon and the closed loops to a plane parallel to XY    *
  424. *    plane (Z = Const plane).                             *
  425. * 2. For each loop find its MaxX while keeping the information on the        *
  426. *    vertex on that extremum.                             *
  427. * 3. For the loop with the biggest MaxX:                     *
  428. *    3.1. Use that extremum vertex (which must be non concave corner) to     *
  429. *         test if loop is in the reverse direction the polygon itself is,    *
  430. *         and reverse it if not.                         *
  431. *    3.2. Fire a ray from the extremum vertex, to the +X direction outside   *
  432. *         of the loop till it intersect the polygon, break the polygon at    *
  433. *         that point and add two edges to beginning of loop from breaking    *
  434. *         point and from end of loop to breaking point (beginning/end point  *
  435. *      of loop is the extremum vertex point).                 *
  436. * 4. Repeat step 3, with all loops.                         *
  437. * 5. Transfrom the new polygon back (using the inverse matrix of step 1)     *
  438. *    to its original orientation.                         *
  439. *                                         *
  440. * Returns TRUE iff the original polygon boundary is in output.             *
  441. *                                         *
  442. *****************************************************************************/
  443. static int CombineClosedLoops(IPPolygonStruct *Pl, InterSegListStruct *PClosed,
  444.                                 int AinB)
  445. {
  446.     RealType MaxX;
  447.     PointType V1, V2, Normal, PlNormal;
  448.     MatrixType RotMat;
  449.     IPVertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
  450.     InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
  451.     *PClosedMaxXLast = NULL;
  452.     InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;
  453.  
  454.     Pl -> Pnext = NULL;          /* Make sure this polygon is disconnected. */
  455.  
  456.     /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
  457.     GenRotateMatrix(RotMat, Pl -> Plane);
  458.     V = VHead = Pl -> PVertex;
  459.     do {                    /* Transform the polygon itself. */
  460.     MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
  461.     V = V -> Pnext;
  462.     }
  463.     while (V != NULL && V != VHead);
  464.  
  465.     PClosedTemp = PClosed;
  466.     while (PClosedTemp != NULL) {        /* And transform the loops also. */
  467.     PISeg = PClosed -> PISeg;
  468.     while (PISeg != NULL) {
  469.         MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  470.         MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  471.  
  472.         PISeg = PISeg -> Pnext;
  473.     }
  474.  
  475.     PClosedTemp = PClosedTemp -> Pnext;
  476.     }
  477.     if (!MatInverseMatrix(RotMat, RotMat))     /* Find the inverse matrix. */
  478.     IritFatalError("CombineClosedLoops: Inverse matrix does not exists");
  479.  
  480.     /* Evalaute the normal to the polygon (which must be convex!). Note we   */
  481.     /* cannt simply use the Plane normal as the polygon was transformed.     */
  482.     V = Pl -> PVertex;
  483.     do {
  484.     Vnext = V -> Pnext;
  485.     PT_SUB(V1, Vnext -> Coord, V -> Coord);
  486.     PT_SUB(V2, Vnext -> Pnext -> Coord, Vnext -> Coord);
  487.     GMVecCrossProd(PlNormal, V1, V2);
  488.     V = Vnext;
  489.     }
  490.     while (PT_LENGTH(PlNormal) < EPSILON);
  491.  
  492.     PClosedTemp = PClosed;
  493.     while (PClosedTemp != NULL) {
  494.     /* Stage 2 - find MaxX extremum value of given loop, test the loop   */
  495.     /* direction, and reverse it if wrong. Note we convert the loop      */
  496.     /* given as InterSegListStruct list into IPVertexStruct list first.  */
  497.     PISegMaxX = PISeg = PClosedTemp -> PISeg;
  498.     MaxX = PISeg -> PtSeg[0][0];          /* Get first vertex X val. */
  499.     PISeg = PISeg -> Pnext;
  500.     while (PISeg)
  501.     {
  502.         if (PISeg -> PtSeg[0][0] > MaxX) {
  503.         MaxX = PISeg -> PtSeg[0][0];
  504.         PISegMaxX = PISeg;
  505.         }
  506.         PISeg = PISeg -> Pnext;
  507.     }
  508.     PClosedTemp -> PISegMaxX = PISegMaxX;
  509.  
  510.     PClosedTemp = PClosedTemp -> Pnext;
  511.     }
  512.  
  513.     /* Stage 3/4 - find the loop with biggest MaxX and combine it with the   */
  514.     /* polygon itself. Do it for all closed loops, in list:             */
  515.     PClosedTemp = PClosed;
  516.     while (PClosed != NULL) {
  517.     /* Find the one with maximum MaxX, and delete it from PClosed list.  */
  518.     PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
  519.     MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
  520.     while (PClosedTemp != NULL)
  521.     {
  522.         if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
  523.         PClosedMaxX = PClosedTemp;
  524.         PClosedMaxXLast = PClosedLast;
  525.         }
  526.         PClosedLast = PClosedTemp;
  527.         PClosedTemp = PClosedTemp -> Pnext;
  528.     }
  529.     if (PClosedMaxX == PClosed)
  530.         PClosed = PClosed -> Pnext;                    /* Del. from */
  531.     else
  532.         PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/
  533.  
  534.     /* Create a vertex list from the loop: */
  535.     V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
  536.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  537.         IritFatalError("CombineClosedLoops: Closed loop with less than 3 vertices");
  538.  
  539.     V = VHead;
  540.     while (V -> Pnext -> Pnext != NULL)
  541.         V = V -> Pnext;                   /* Go to last pt. */
  542.     IPFreeVertex(V -> Pnext);        /* and free - same as first. */
  543.     V -> Pnext = VHead;               /* Make vertex list circular. */
  544.  
  545.     PISegMaxX = PClosedMaxX -> PISegMaxX;
  546.  
  547.     /* Now test if the vertex list should be reversed. Find the vertices */
  548.     /* which form the PISegMaxX segment, so V -> Pnext is the first      */
  549.         /* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext   */
  550.         /* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form     */
  551.     /* convex corner which we use to test if loop needs to be reversed:  */
  552.     while (!PT_APX_EQ(V -> Pnext -> Coord, PISegMaxX -> PtSeg[0]))
  553.             V = V -> Pnext;
  554.     VMaxX = V -> Pnext;
  555.  
  556.     /* Prepare in point in REAL position. */
  557.     PT_COPY(VStruct.Coord, V -> Coord);
  558.     MatMultVecby4by4(VStruct.Coord, VStruct.Coord, RotMat);
  559.     VStruct.Pnext = NULL;
  560.     if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
  561.         /* The Inside of the object is actually the loop itself. In that */
  562.         /* case we simply return all the loops converted into polygon.   */
  563.         /* This case is simple...                         */
  564.         IPFreeVertexList(VHead);           /* Free loop vertex list. */
  565.         PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
  566.         PClosedTemp = PClosed = PClosedMaxX;
  567.         while (PClosedTemp != NULL) {    /* Transform the loops back. */
  568.         PISeg = PClosed -> PISeg;
  569.         while (PISeg != NULL) {
  570.             MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  571.             MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  572.  
  573.             PISeg = PISeg -> Pnext;
  574.         }
  575.         PClosedTemp = PClosedTemp -> Pnext;
  576.         }
  577.  
  578.         ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
  579.         return FALSE;       /* Boundary is NOT part of object result. */
  580.     }
  581.     PT_SUB(V1, VMaxX -> Coord, V -> Coord);
  582.     PT_SUB(V2, VMaxX -> Pnext -> Coord, VMaxX -> Coord);
  583.     GMVecCrossProd(Normal, V1, V2);
  584.     if (DOT_PROD(Normal, PlNormal) > 0) {        /* Need to reverse list. */
  585.         Vprev = VHead;
  586.         V = Vprev -> Pnext;
  587.         Vnext = V -> Pnext;
  588.         do {
  589.         V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
  590.         Vprev = V;
  591.         V = Vnext;
  592.         Vnext = V -> Pnext;
  593.         }
  594.         while (Vprev != VHead);
  595.     }
  596.  
  597.     PISeg = PClosedMaxX -> PISeg;  /* Time to free the InterSegmentList: */
  598.     while (PISeg != NULL) {
  599.         PItemp = PISeg;
  600.         PISeg = PISeg -> Pnext;
  601.         IritFree((VoidPtr) PItemp);
  602.     }
  603.     IritFree((VoidPtr) PClosedMaxX);
  604.  
  605.     /* O.k. lets fire a ray from VMaxX to +X direction and see where it  */
  606.     /* intersects the polygon. The routine CutPolygonAtRay will add two  */
  607.     /* vertices at the ray intersection into polygon vertex list and     */
  608.     /* return a pointer to first one, so we can chain our loop directly  */
  609.     /* between these two new vertices.                     */
  610.     V = CutPolygonAtRay(Pl, VMaxX -> Coord);
  611.     Vnext = V -> Pnext;
  612.     /* Introduce a copy of VMaxX and successor to VMaxX: */
  613.     VMaxX -> Pnext = IPAllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
  614.                                 VMaxX -> Pnext);
  615.     PT_COPY(VMaxX -> Pnext -> Coord, VMaxX -> Coord);
  616.     PT_CLEAR(VMaxX -> Pnext -> Normal);
  617.     V -> Pnext = VMaxX -> Pnext;
  618.     IP_SET_INTERNAL_VRTX(V);
  619.     VMaxX -> Pnext = Vnext;
  620.     IP_SET_INTERNAL_VRTX(VMaxX);
  621.     }
  622.  
  623.     /* Stage 5 - Time to rotate polygon back to its original position. */
  624.     V = VHead = Pl -> PVertex;
  625.     do {
  626.     MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
  627.     V = V -> Pnext;
  628.     }
  629.     while (V != NULL && V != VHead);
  630.  
  631.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  632.     IP_RST_CONVEX_POLY(Pl);         /* This polygon is not convex any more. */
  633.  
  634.     return TRUE;
  635. }
  636.  
  637. /*****************************************************************************
  638. *   Push on the adjacency stack, all adjacent polygons which are complete    *
  639. * (no intersection) and are adjacent to complete edges (originated from         *
  640. * input polygons) of the given polygon.                         *
  641. *****************************************************************************/
  642. static void PushAdjOnStack(IPPolygonStruct *Pl, IPPolygonStruct *AdjStack[],
  643.                              int *StackPointer)
  644. {
  645.     IPVertexStruct
  646.     *V = Pl -> PVertex;
  647.  
  648.     do {
  649.     /* If you wants to propagate iff both vertices are original then     */
  650.     /* uncomment the next line.                         */
  651.     if (IS_ORIGINAL_VRTX(V) /* && IS_ORIGINAL_VRTX(V -> Pnext) */
  652.         && V -> PAdj != NULL)
  653.         AdjStack[++*StackPointer] = V -> PAdj;
  654.     if (*StackPointer >= ADJ_STACK_SIZE) {
  655.         IritFatalError("Adjacency stack overflow, object too big");
  656.     }
  657.     V = V -> Pnext;
  658.     }
  659.     while (V != Pl -> PVertex);
  660. }
  661.  
  662. /*****************************************************************************
  663. *   Chain two Polygon lists into one. For fast processing it is prefered the *
  664. * first one to be to shorter. Returns pointer to chained list.             *
  665. *****************************************************************************/
  666. static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
  667.                        IPPolygonStruct *Pl2)
  668. {
  669.     IPPolygonStruct *Ptemp;
  670.  
  671.     if (Pl1 == NULL)
  672.         return Pl2;
  673.     else if (Pl2 == NULL)
  674.     return Pl1;
  675.     else {
  676.     Ptemp = Pl1;
  677.     while (Ptemp -> Pnext != NULL)
  678.         Ptemp = Ptemp -> Pnext;
  679.     Ptemp -> Pnext = Pl2;
  680.     return Pl1;
  681.     }
  682. }
  683.  
  684. /*****************************************************************************
  685. *   This routine coordinates all the extraction of the polygons from the     *
  686. * intersecting lists. Does it in the following steps:                 *
  687. * 1. Mark all polygons with no intersection at all as complete polygons.     *
  688. *    (this is cause that this polygon will be totally in or out, according   *
  689. *    to inter-polygon adjacencies propagation...)                 *
  690. *    Also Mark them as undefined (if in output or undefined) yet.         *
  691. *    Uses IPPolygonStruct Tags to save these bits.                 *
  692. * 2. 2.1. Convert the unordered segment list of each polygon to closed loops *
  693. *         (if create a hole in polygon) or open (if crosses its boundary).   *
  694. *    2.2. Order the open loops along the perimeter of the polygon (note      *
  695. *      these loops cannt intersect. For example (5 vertices polygon):     *
  696. *             -----------------------------L3                 *
  697. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  698. *        | |               |  |     |  |         |        |   |  |    *
  699. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  700. *         Note L1, L2 are enclosed in L3 loop, and that the order is circular*
  701. *    2.3. "Break" the polygon at each open loop that has no enclosed loops   *
  702. *      in it. For example we can start at L1, L2, L4, L5 and then L3.     *
  703. *      "Break" means - replace the vertex chain between the two loop end  *
  704. *      points, with the loops itself. Depends upon the relation required  *
  705. *      we may need to output a new polygon form from the deleted chain    *
  706. *      and that loop. In addition we may form a new polygon from last     *
  707. *      loop and was was left from the original polygon             *
  708. *      For each formed polygon, for each complete edge of it (i.e. edge   *
  709. *      which was originally in the polygon) test the adjacent polygon     *
  710. *      if it is complete (as marked in 1.) and if in or undefined (marked *
  711. *      undefined in 1.) is still undefined:                     *
  712. *      2.3.1. set it to be in.                         *
  713. *      2.3.2. push it on adjacency stack.                     *
  714. *    2.4. For each closed loop - find in which polygon (from polygons         *
  715. *      created in 2.3.) it is enclosed, and decompose it.             *
  716. * 3. While adjacencies stack not empty do:                     *
  717. *    3.1. pop top polygon from stack and output it.                 *
  718. *    3.2. For each of its edges (which obviousely must be complete edges)    *
  719. *      if adjacent polygon is complete and undefined:             *
  720. *      3.3.1. set it to be in.                         *
  721. *      3.3.2. push it on adjacency stack.                     *
  722. *    3.3  go back to 3.                                 *
  723. *                                         *
  724. *   The above algorithm defines in as in output, but dont be confused with   *
  725. * the required inter-object AinB (or AoutB if FALSE), which used to         *
  726. * determine which side of the trimming loop should be output.             *
  727. *   Note this routine may return non-convex polygons (but marked as so) even *
  728. * though the input for the booleans must be convex polygons only!         *
  729. *   In order to keep the given object unchanged, a whole new copy off the    *
  730. * polygon list is made. The polygons of the list that are not in the output  *
  731. * are freed: a global list of all polygons (pointers) is used to scan them   *
  732. * in the end and free the unused ones (list PolysPtr).                 *
  733. *****************************************************************************/
  734. IPObjectStruct *ExtractPolygons(IPObjectStruct *PObj, int AinB)
  735. {
  736.     int NumOfPolys = 0,
  737.     StackPointer = -1;
  738.     IPPolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl,
  739.         *Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
  740.     IPVertexStruct *V, *Vnext;
  741.     InterSegListStruct *PClosed, *POpen, *Ptemp;
  742.  
  743. #ifdef DEBUG3
  744.     printf("Enter ExtractPolygons\n");
  745. #endif /* DEBUG3 */
  746.  
  747.     /* Stage 1. - mark all polygons as needed: */
  748.     PlHead = Pl = PObj -> U.Pl;
  749.     /* Gen. a copy of Pl, so we can modify the original polygon list: */
  750.     PObj -> U.Pl = CopyPolygonList(Pl);
  751.  
  752.     while (Pl != NULL) {
  753.     NumOfPolys++;         /* Count number of polygons in original object. */
  754.     if (Pl -> PAux != NULL) {     /* The intersection list is not empty! */
  755.         RST_COMPLETE_POLY(Pl);     /* Mark it as non complete polygon. */
  756.         V = Pl -> PVertex;
  757.         do {
  758.         SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
  759.         V = V -> Pnext;
  760.         }
  761.         while (V != Pl -> PVertex);
  762.     }
  763.     else {
  764.         SET_COMPLETE_POLY(Pl);         /* Mark it as complete polygon. */
  765.         RST_INOUTPUT_POLY(Pl);     /* And as undefined (if in output). */
  766.         RST_ADJPUSHED_POLY(Pl);     /* And as not pushed on adj. stack. */
  767.     }
  768.     Pl = Pl -> Pnext;
  769.     }
  770.  
  771.     /* Stage 2. - scan the polygons and subdivide the intersecting ones: */
  772.     Pl = PlHead;
  773.  
  774.     /* We will save pointers to ALL polygons in list so we could free in the */
  775.     /* end the ones that are not in the output list, and therefore unused.   */
  776.     PolysPtr = (IPPolygonStruct **)
  777.         IritMalloc(sizeof(IPPolygonStruct *) * NumOfPolys);
  778.     NumOfPolys = 0;
  779.  
  780.     while (Pl != NULL) {
  781.     PolysPtr[NumOfPolys++] = Pl;        /* Save pointer to this polygon. */
  782.  
  783.     PlNext = Pl -> Pnext;
  784.     Pl -> Pnext = NULL;
  785.  
  786.     if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
  787.         /* Convert the intersecting segments into open/closed loops. */
  788.         LoopsFromInterList(Pl, &PClosed, &POpen);
  789.  
  790.         /* Save copy of original polygon vertex list as we need its      */
  791.         /* normals to interpolate for the internal ones.             */
  792.         OriginalPl = IPAllocPolygon(1, Pl -> Tags,
  793.                     CopyVertexList(Pl -> PVertex), NULL);
  794.         IP_RST_BBOX_POLY(OriginalPl);
  795.         PLANE_COPY(OriginalPl -> Plane, Pl -> Plane);
  796.  
  797.         if (POpen != NULL) {
  798.         /* Sort the Open loops into an order we can handle... */
  799.         SortOpenInterList(Pl, &POpen);
  800.         SplPl = NewPl = NULL;     /* Keep the list of split polygons. */
  801.  
  802.         while (POpen != NULL) {    /* Clip the open loops from polygon: */
  803.             /* Note ClipOpenLoopFromPoly also frees the InterSegment */
  804.             /* list pointed by POpen (but not POpen itself).          */
  805.             NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
  806.             if (NewPl != NULL) {   /* If loop clipped a new polygon, */
  807.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  808.             NewPl -> Pnext = SplPl;/* add to split polygon list. */
  809.             SplPl = NewPl;
  810.             /* And push adj. polygons of complete edges on stack.*/
  811.             PushAdjOnStack(NewPl, AdjStack, &StackPointer);
  812.             }
  813.             Ptemp = POpen;
  814.             POpen = POpen -> Pnext;
  815.             IritFree((VoidPtr) Ptemp);
  816.         }
  817.  
  818.         /* Last clip generated nothing (NewPl == NULL) so part that  */
  819.         /* left from Pl (PlCopy) is IN output list! Add this poly:   */
  820.         if (NewPl == NULL) {
  821.             PLANE_COPY(Pl -> Plane, OriginalPl -> Plane);
  822.             Pl -> Pnext = SplPl; /* And chain what was left from it. */
  823.             SplPl = Pl;
  824.             /* And push adjacent polygons of complete edges on stack.*/
  825.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  826.             SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
  827.             IP_RST_CONVEX_POLY(Pl);       /* May be not convex now. */
  828.         }
  829.  
  830.         UpdateVerticesNormals(SplPl, OriginalPl);
  831.         }
  832.         else
  833.         SplPl = Pl;
  834.  
  835.         if (PClosed != NULL) {
  836.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext)
  837.             Pl -> PAux = NULL;
  838.  
  839.         /* Classify the closed loops into the appropriate polygon. */
  840.         while (PClosed != NULL) {
  841.             Ptemp = PClosed -> Pnext;
  842.             for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  843.             if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0],
  844.                         0) % 2 == 1) {
  845.                 /* This closed loop is contained in this polygon.*/
  846.                 PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux;
  847.                 Pl -> PAux = (VoidPtr) PClosed;
  848.                 break;
  849.             }
  850.             }
  851.             if (Pl == NULL) {
  852.             /* This closed loop is part of a trimmed out by open */
  853.             /* loop region. It should be only the island formed  */
  854.             /* by this closed loop then.                 */
  855.             /* Make a new polygon - a copy of the original and   */
  856.             /* Put this loop in it.                     */
  857.             NewPl = IPAllocPolygon(1, OriginalPl -> Tags,
  858.                 CopyVertexList(OriginalPl -> PVertex), NULL);
  859.             IP_RST_BBOX_POLY(NewPl);
  860.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  861.             NewPl -> PAux = (VoidPtr) PClosed;
  862.             NewPl -> Pnext = SplPl;
  863.             SplPl = NewPl;
  864.             }
  865.             PClosed = Ptemp;
  866.         }
  867.  
  868.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  869.             /* Make a "cut" from the loop(s)  +-------+    +-------+ */
  870.             /* to boundary if possible, and   |       |    |       | */
  871.             /* converting Pl to a nonconvex   |  / \  | -> |  / \__| */
  872.             /* polygon, that has an edge (the |  \ /  | -> |  \ /  | */
  873.             /* cut) which is shared twice in  |       |    |       | */
  874.             /* the same polygon              +-------+    +-------+ */
  875.             PClosed = (InterSegListStruct *) Pl -> PAux;
  876.             Pl -> PAux = NULL;
  877.             if (CombineClosedLoops(Pl, PClosed, AinB)) {
  878.             /* If returned with TRUE -  polygon boundary is in   */
  879.             /* output, so add all its neighbours to adj. stack.  */
  880.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  881.             }
  882.  
  883.             UpdateVerticesNormals(Pl, OriginalPl);
  884.         }
  885.         }
  886.  
  887.         OutputPl = ChainPolyLists(SplPl, OutputPl);
  888.  
  889.         /* Free the original polygon vertex list. */
  890.         IPFreePolygon(OriginalPl);
  891.     }
  892.  
  893.     Pl = PlNext;
  894.     }
  895.  
  896.     /* Stage 3. - handling adjacencies and propagate them in polygons:         */
  897.     /* Pop off the elements from the stack, and propagate them using their   */
  898.     /* adjacencies.                                 */
  899.     while (StackPointer >= 0) {
  900.     Pl = AdjStack[StackPointer--];             /* Pop top element. */
  901.     if (!IS_COMPLETE_POLY(Pl) ||        /* Ignore non complete polygons. */
  902.          IS_INOUTPUT_POLY(Pl))
  903.         continue;                  /* If already handled. */
  904.  
  905.     SET_INOUTPUT_POLY(Pl);      /* Mark this one as handled for next time. */
  906.  
  907.     V = Pl -> PVertex;   /* Push all adjacent ones that not handled yet. */
  908.     do {
  909.         if (V -> PAdj &&
  910.         IS_COMPLETE_POLY(V -> PAdj) &&
  911.         !IS_INOUTPUT_POLY(V -> PAdj) &&
  912.         !IS_ADJPUSHED_POLY(V -> PAdj)) {
  913.         SET_ADJPUSHED_POLY(V -> PAdj);
  914.         AdjStack[++StackPointer] = V -> PAdj;   /* Push it on stack. */
  915.         if (StackPointer >= ADJ_STACK_SIZE)
  916.             IritFatalError("Adjacency stack overflow, object too big");
  917.         }
  918.         V = V -> Pnext;
  919.     }
  920.     while (V != Pl -> PVertex);
  921.  
  922.     Pl -> Pnext = OutputPl;           /* And chain it into output list. */
  923.     OutputPl = Pl;
  924.     }
  925.  
  926.     /* Free all polygons which are not in the output list: */
  927.     while (--NumOfPolys >= 0) {
  928.     if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
  929.         IPFreePolygon(PolysPtr[NumOfPolys]);
  930.     }
  931.     }
  932.     IritFree((VoidPtr) PolysPtr);
  933.  
  934.     /* Another floating point kludge: a polygon may have zero length edge so */
  935.     /* search for those and remove them - someone may die because of one...  */
  936.     Pl = OutputPl;
  937.     while (Pl != NULL) {
  938.     V = Pl -> PVertex;
  939.     do {
  940.         Vnext = V -> Pnext;
  941.         if (PT_APX_EQ(V -> Coord, Vnext -> Coord)) {
  942.         /* Ahh - we got you. Simply skip Vnext vertex and free it: */
  943.         V -> Pnext = Vnext -> Pnext;
  944.         /* Update polygon vertex pointer if point on freed vertex: */
  945.         if (Pl -> PVertex == Vnext)
  946.             Pl -> PVertex = Vnext -> Pnext;
  947.         IPFreeVertex(Vnext);
  948.         Vnext = V -> Pnext;
  949.         }
  950.         V = Vnext;
  951.     }
  952.     while (V != Pl -> PVertex && V != NULL);
  953.  
  954.     Pl = Pl -> Pnext;
  955.     }
  956.  
  957. #ifdef DEBUG3
  958.     printf("Exit ExtractPolygons\n");
  959. #endif /* DEBUG3 */
  960.  
  961.     return GenPolyObject("", OutputPl, NULL);     /* Return resulting object. */
  962. }
  963.  
  964. #ifdef DEBUG2
  965.  
  966. /*****************************************************************************
  967. *   Print the content of the given polygon, to standard output.             *
  968. *****************************************************************************/
  969. static void PrintVrtxList(IPVertexStruct *V)
  970. {
  971.     IPVertexStruct
  972.     *VHead = V;
  973.  
  974.     do {
  975.     printf("    %12lf %12lf %12lf",
  976.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  977.     if (IS_INTERNAL_EDGE(V))
  978.         printf(" (Internal)\n");
  979.     else
  980.         printf("\n");
  981.     V = V -> Pnext;
  982.     }
  983.     while (V!= NULL && V != VHead);
  984. }
  985.  
  986. /*****************************************************************************
  987. *   Print the content of the given InterSegment list, to standard output.    *
  988. *****************************************************************************/
  989. static void PrintInterList(InterSegmentStruct *PInt)
  990. {
  991.     printf("INTER SEGMENT LIST:\n");
  992.  
  993.     if (PInt)
  994.     printf("Entry vertex pointer %p\n", PInt -> V[0]);
  995.     while (PInt) {
  996.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  997.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  998.         FP_SEG(PInt->V[0]),
  999.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  1000.         FP_SEG(PInt->V[1]));
  1001.     if (PInt -> Pnext == NULL)
  1002.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  1003.  
  1004.     PInt = PInt -> Pnext;
  1005.     }
  1006. }
  1007.  
  1008. #endif /* DEBUG2 */
  1009.